/* *
* 时间复杂度为 O(nlogn) 或 O(n^2) 空间复杂度为 O(logn) 不稳定
* 快速排序的基本思想是选择一个基准元素，在每一轮划分中将数组分为两个部分，其中一部分的所有元素都小于等于基准元素，另一部分的所有元素都大于基准元素。然后递归地对两个部分继续进行划分，直到每个部分只有一个元素或为空。
* */
function quickSort(arr) {
    //? 递归出口 arr分不了左右了
    if (arr.length <= 1) return arr
    const base = arr[0]
    let left = []
    let right = []
    for (let i = 1; i < arr.length; i ++) {
        if (arr[i] < base) left.push(arr[i])
        else right.push(arr[i])
    }
    return [...quickSort(left), base, ...quickSort(right)]
}
const arr = [5,2,6,1,7,2,10,8]
console.log(quickSort(arr));
